/*!
 * \file heurColoring.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Heuristics for coloring, maximum stable set and maximum clique.
 */

#include <stdlib.h>
#include <bitmap.h>
#include <graph.h>
#include <heurColoring.h>

static NODETYPE * BB; //!< Auxiliary bitmap used in various heuristics.
static NODETYPE * CC; //!< Auxiliary bitmap used in various heuristics.
static Graph * heurg; //!< Input graph of the heuristics.
static size_t memsz = 0; //!< Memory space used by the heuristics.

// mcsColoring
static int * nextInColor = NULL; //!< Vertices classified by colors

// fracColoring
//static NODETYPE * E = NULL;	//!< Auxiliary bitmap used in \c fracColoring.
//static NODETYPE * EE;		//!< Auxiliary bitmap used in \c fracColoring.
//static NODETYPE * S;		//!< Auxiliary bitmap used in \c fracColoring.

void initHeur(Graph * g) {
	heurg = g;
	int nnodes = NODEIDX(g->n-1) + 1;
	BB = (NODETYPE *) calloc(nnodes, WSIZE);
	CC = (NODETYPE *) calloc(nnodes, WSIZE);
	memsz += (nnodes << LOGW);
	nextInColor = NULL;
}

void closeHeur() {
	free(BB);
	free(CC);
	BB = NULL;
	CC = NULL;
	heurg = NULL;

	if (nextInColor != NULL) {
		free(nextInColor);
		nextInColor = NULL;
	}

//	if (E != NULL) {
//		free(E);
//		E = NULL;
//		EE = NULL;
//	}
}

size_t getMemSize() {
	return memsz;
}

int greedyColoring(NODETYPE * B, int lim, int minBNode, int maxBNode, int * R,
		int * C) {
	int size = 0;
	int i = 0;
	int vidx = 0;
	int nodeidx;
	NODETYPE * nodeCC;
	NODETYPE * nodeBB;

	int minCCNode = minBNode;
	int maxCCNode = maxBNode;
	copyAll(CC, B, minCCNode, maxCCNode + 1);
	while (minCCNode <= maxCCNode) {
		size++;
		nodeidx = minCCNode;
		copyAll(BB, CC, nodeidx, maxCCNode + 1);
		nodeBB = (BB + nodeidx);
		vidx = NODELEAST(*nodeBB);
		while (vidx >= 0) {
			int v = NELEM(nodeidx) + vidx;
			if (size > lim) {
				R[i] = v;
				C[i++] = size - lim;
			}
			removeAll(BB, NEIG(heurg, v), nodeidx, maxCCNode + 1);
			*nodeBB = DELFROMNODE(*nodeBB, vidx);
			nodeCC = (CC + nodeidx);
			*nodeCC = DELFROMNODE(*nodeCC, vidx);
			nodeidx = minNode(BB, nodeidx, maxCCNode);
			nodeBB = (BB + nodeidx);
			vidx = NODELEAST(*nodeBB);
		}
		minCCNode = minNode(CC, minCCNode, maxCCNode);
		maxCCNode = maxNode(CC, maxCCNode, minCCNode);
	}

	return i;
}

/*!
 * \fn int maxClique(NODETYPE * B, int minBNode, int maxBNode)
 * \brief Greedy heuristic for maximum clique.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum clique.
 *
 * If \c B[\c *minBNode\c ] \c == \c 0, then an error may occur.
 *
 * \param B Input bitmap of vertices to color.
 * \param minBNode Smallest index of a non-zero node of the input bitmap.
 * \param maxBNode Greates index of a non-zero node of the input bitmap.
 *
 * \return The size of the clique found.
 */
int maxClique(NODETYPE * B, int minBNode, int maxBNode) {
	int nodeidx = minBNode;
	copyAll(BB, B, nodeidx, maxBNode + 1);

	NODETYPE * nodeBB = (BB + nodeidx);
	int vidx = NODELEAST(*nodeBB);
	int size = 0;
	while (vidx >= 0) {
		size++;
		retainAll(BB, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx, maxBNode + 1);
		*nodeBB = DELFROMNODE(*nodeBB, vidx);
		nodeidx = minNode(BB, nodeidx, maxBNode);
		nodeBB = (BB + nodeidx);
		vidx = NODELEAST(*nodeBB);
	}

	return size;
}

static void mcsRecolor(NODETYPE * B, int * minBNode, int * maxBNode, int size) {
	int vidx, v = 0;
	int vnode;
	int lastnodeidx = -1;
	NODETYPE * nodeBB;
	int sentinel = heurg->n << 1;

	int u = 0, prevu;
	copyAll(BB, B, *minBNode, *maxBNode + 1);
	vnode = *minBNode;
	nodeBB = (BB + vnode);
	vidx = NODELEAST(*nodeBB);
	while (vidx >= 0) {
		int ucolor = 1;
		while (ucolor < size) {
			int curInColor = nextInColor[heurg->n + ucolor];
			int prevInColor = heurg->n + ucolor;
			int hasNeig = 0;
			v = NELEM(vnode) + vidx;
			while (hasNeig < 2 && curInColor < heurg->n) {
				if (HASEDGE(heurg, v, curInColor)) {
					hasNeig++;
					u = curInColor;
					prevu = prevInColor;
				}
				prevInColor = curInColor;
				curInColor = nextInColor[curInColor];
			}

			if (hasNeig < 2) {
				int w = 0, wcolor = 0;
				if (hasNeig == 0) {
					w = v;
					wcolor = ucolor;
				} else {
					int cl = ucolor + 1;
					while (cl <= size) {
						int cc = nextInColor[heurg->n + cl];
						while (cc < sentinel && !HASEDGE(heurg,u,cc))
							cc = nextInColor[cc];
						if (cc == sentinel) {
							w = u;
							wcolor = cl;
							nextInColor[prevu] = nextInColor[u];
							nextInColor[v] = nextInColor[heurg->n + ucolor];
							nextInColor[heurg->n + ucolor] = v;
							cl = size;
						}
						cl++;
					}
				}

				if (wcolor >= 1) {
					nextInColor[w] = nextInColor[heurg->n + wcolor];
					nextInColor[heurg->n + wcolor] = w;
					*nodeBB = DELFROMNODE(*nodeBB, vidx);
					*(B + vnode) = DELFROMNODE(*(B + vnode), vidx);
					lastnodeidx = vnode;
					ucolor = size;
					vidx = -1;
				}
			}
			ucolor++;
		}

		if (vidx >= 0)
			retainAll(BB, NEIG(heurg, v), vnode, *maxBNode + 1);
		else
			vidx = NODEIDX(v);
		if (*nodeBB)
			vidx = NODENEXTLEAST(*nodeBB, vidx);
		else
			vidx = -1;
		while (vidx < 0 && vnode < *maxBNode) {
			nodeBB = (BB + (++vnode));
			vidx = NODELEAST(*nodeBB);
		}
	}

	if (lastnodeidx >= 0) {
		*minBNode = minNode(B, *minBNode, *maxBNode);
		*maxBNode = maxNode(B, *maxBNode, *minBNode);
	}
}

static int partialColoring(NODETYPE * B, int lim, int * minBNode,
		int * maxBNode) {
	int size = 0;
	int vidx = 0;
	int nodeidx;
	NODETYPE * nodeCC;
	NODETYPE * nodeBB;
	int sentinel = heurg->n << 1;

	if (nextInColor == NULL) {
		nextInColor = (int *) calloc((heurg->n + 1) << 1, sizeof(int));
		memsz += (((heurg->n + 1) * sizeof(int)) << 1);
	}

	copyAll(CC, B, *minBNode, *maxBNode + 1);
	while (size < lim && *minBNode <= *maxBNode) {
		nextInColor[heurg->n + (++size)] = sentinel;

		nodeidx = *minBNode;
		copyAll(BB, CC, nodeidx, *maxBNode + 1);
		nodeBB = (BB + nodeidx);
		vidx = NODELEAST(*nodeBB);
		while (vidx >= 0) {
			int v = NELEM(nodeidx) + vidx;
			removeAll(BB, NEIG(heurg, v), nodeidx, *maxBNode + 1);
			*nodeBB = DELFROMNODE(*nodeBB, vidx);
			nodeCC = (CC + nodeidx);
			*nodeCC = DELFROMNODE(*nodeCC, vidx);

			nextInColor[v] = nextInColor[heurg->n + size];
			nextInColor[heurg->n + size] = v;

			nodeidx = minNode(BB, nodeidx, *maxBNode);
			nodeBB = (BB + nodeidx);
			vidx = NODELEAST(*nodeBB);
		}
		*minBNode = minNode(CC, *minBNode, *maxBNode);
		*maxBNode = maxNode(CC, *maxBNode, *minBNode);
	}

	return size;
}

int mcsColoring(NODETYPE * B, int lim, int minRNode, int maxRNode, int * R,
		int * C) {
	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
		return greedyColoring(B, lim, minRNode, maxRNode, R, C);

	int i = partialColoring(B, lim, &minRNode, &maxRNode);
	if (minRNode <= maxRNode && lim == i) {
		mcsRecolor(CC, &minRNode, &maxRNode, lim);
		return greedyColoring(CC, 0, minRNode, maxRNode, R, C);
	}

	return 0;
}

int mcsColoring_f(NODETYPE * B, int lim, int minRNode, int maxRNode, int * R,
		int * C) {
	if (lim <= 1)
		return greedyColoring(B, lim, minRNode, maxRNode, R, C);

	int i = partialColoring(B, lim, &minRNode, &maxRNode);
	if (minRNode <= maxRNode && lim == i) {
		mcsRecolor(CC, &minRNode, &maxRNode, lim);
		return greedyColoring(CC, 0, minRNode, maxRNode, R, C);
	}

	return 0;
}
